package com.li.suanfa;

import java.util.Arrays;
import java.util.Random;

/**  
* 类说明   
*  
* @author ****  
* @date 2018年4月1日  新建  
*/
public class MergeSort {
	public static final int SIZE = 10;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		System.out.println(Arrays.toString(array));
		long time1= System.currentTimeMillis();
		mergeSort(array,0,array.length-1);
		System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}
	public static void mergeSort(int[] a ,int low ,int high){
		if(low>=high){
			return;
		}
		int mid = (low+high)/2;
		mergeSort(a, low, mid);
		mergeSort(a, mid+1, high);
		merge(a,low,mid,high);
	}
	
	public static void merge(int[] a,int low,int mid,int high){
		int i = low;
		int j = mid+1;
		int[] temp = new int[high-low+1];
		int index = 0;
		while(i<=mid && j<=high){
			temp[index++] = a[i] < a[j]? a[i++]:a[j++];
		}
		while(i<=mid){
			temp[index++] = a[i++];
		}
		while(j<=high){
			temp[index++] = a[j++];
		}
		for(int k=0;k<temp.length;k++){
			a[low++] = temp[k];
		}
	}
}
  